1. Field of the Invention
This invention relates to methods and systems that efficiently use a processor to perform convolution operations, and particularly to communication systems such as modems that perform such operations in interpreting communication signals.
2. Description of Related Art
Many digital signal processing systems execute routines that require repeated summing of products. For example, communication systems including modems often convert communication signals to sequences or digital samples and then filter and transform the sequences to extract data. Encoding data for transmission requires similar digital processing. The specific processing required depends on the particular protocols implemented in a communication signal, but such processing often includes finite impulse response (FIR) filtering, fast Fourier transforms (FFTs), and spectral analysis. The term "convolution operation" as used herein refers to FIR filters, FFTs, and similar processing operations that determine of a series of sums. Equation 1 illustrates a sum basic for a convolution operation. ##EQU1##
In Equation 1, s.sub.in is an input sequence, s.sub.k is a sequence that depends on index k, and s is a sequence that is the convolution of sequences s.sub.in and s.sub.k. Although Equation 1 shows the range of the summation as infinite, the actual range is limited to a range of interest or a range where both sequences s.sub.k (i) and s.sub.k (i) are non-zero. An example application is a Fourier transform where sequence s.sub.in is time-domain sequence to be transformed, sequence s.sub.k represents a function associated with frequency k, and sequence s is the Fourier transform of s.sub.in. Complete generation of the convolution s requires repeating the sum of Equation 1 for every value of k that is of interest.
A finite impulse response (FIR) filter is a type of convolution commonly used for filtering sequences. Equation 2 shows a summation for an M-tap FIR filter. ##EQU2##
In Equation 2, values C(0) to C(M-1) are filter coefficients of the FIR filter, values S(k-i) are from a sequence being filter, and value F(k) is the filtered value for index value k. Generally, a FIR filter operation repeats the summation of Equation 2 N times to generate as a sequence of filtered values F(k) for index k equal to 0 to N-1.
Table 1 contains a C programming language routine that generates N filtered values using an M-tap FIR filter operation according to Equation 2.
TABLE 1 for (k=0; k&lt;N; k++) , { F[k] = 0; for (i = 0; i&lt;M; i++) F[k] += C[i]*S[k-i]; /*sum instruction*/ }
The routine of Table 1 executes a sum instruction N*M times. In a typical processing system, repeated execution of the sum instruction requires 2*M*N memory loads for filter coefficients C[i] and input values S[k=i], M*N multiplications, M*N additions, and M*N memory stores for accumulate filtered values F[k]. The routine of Table 1 is memory I/O bound in that the number of memory accesses (3M*N) is greater than the number of arithmetic operations (2M*N).
Memory access times are critical to the performance of a memory I/O bound operations such as the FIR filter routine of Table 1. However, for most systems, memory access times are slow because a typical memory system for a processor is much slower than the processor's operating frequency. Fast memory caches improve access times, but when N or M is large, the cache may be insufficient to hold the filter coefficients and the data being filtered. Thus, cache misses result, and the filter operations require frequent access to slower memory. Processes that require fewer memory accesses and improve performance of convolution operations are sought.